W12. Grammars and Computability

1. Theory

1.1 Thompson’s Construction: From Regular Expression to ε-NFSA

1.1.1 Motivation and Overview

Given a regular expression over an alphabet, we often need a computational device — a finite automaton — that accepts exactly the language the expression describes. Thompson’s Construction is a classical algorithm that converts any regular expression into an equivalent ε-Nondeterministic Finite State Automaton (ε-NFSA). The resulting automaton can then be used to match strings against the original regular expression (this is precisely how most regular-expression engines work internally).

The algorithm works recursively: a regular expression is broken into its constituent subexpressions, an automaton fragment is built for each, and the fragments are combined using a fixed set of composition rules. Every subexpression produces an automaton with exactly one start state and one accepting state (with no transitions entering the start state or leaving the accepting state from outside the fragment). This structural discipline makes recursive composition straightforward.

1.1.2 Base Case Rules

There are two base cases that handle atomic regular expressions.

The empty expression . The regular expression (recognising only the empty string) is converted to a two-state automaton: a start state and an accepting state connected by a single -transition.

Thompson’s rule for ε: a single ε-transition

A single symbol . A symbol from the input alphabet is converted to a two-state automaton with a single -labelled transition from the start state to the accepting state .

Thompson’s rule for a single symbol a

1.1.3 Composition Rules

Given automata and for subexpressions and , three rules cover all compound expressions.

Concatenation . The accepting state of is merged with (or connected by an -transition to) the start state of . The resulting automaton starts where starts and accepts where accepts. Informally: first consume a string from , then consume a string from .

Thompson’s rule for concatenation st: the two fragments are chained end-to-start

Union . A new start state is introduced with two -transitions leading into the start states of and respectively. A new accepting state is introduced, with -transitions from the accepting states of both and into . The resulting automaton non-deterministically guesses which alternative to pursue.

Thompson’s rule for union s|t: a new start fans out, both branches converge to a new accept state

Kleene star . A new start state and a new accepting state are introduced. An -transition connects directly to (allowing zero repetitions). An -transition connects to the start of , and an -transition connects the accepting state of back to the start of (allowing repetition) and also forward to .

Thompson’s rule for Kleene star s*: loop back from the end of N(s) to its start, plus a bypass for zero repetitions

1.1.4 Properties of the Construction

The ε-NFSA produced by Thompson’s Construction has a number of useful structural properties: it has at most states for a regular expression of length ; each state has at most two outgoing -transitions; and no -transition ever enters the overall start state or leaves the overall accepting state. These properties guarantee that composition steps remain well-defined at every level of recursion.

1.2 Kleene’s Algorithm: From FSA to Regular Expression

1.2.1 Overview

The converse problem — given a finite automaton, find a regular expression that describes its language — is solved by Kleene’s Algorithm (sometimes called the state elimination algorithm in variants). Given an FSA with states , the algorithm systematically computes, for each pair and each , the set :

Each such set is represented as a regular expression. The algorithm computes these expressions step by step for .

Because no state has index greater than , the expression describes every string that takes from its start state to state with no restriction on intermediate states. If is the set of accepting states, then:

1.2.2 Initial Expressions ()

For , paths use no intermediate states at all — only direct transitions:

The in the self-loop case reflects the fact that zero steps (staying in ) is always possible.

1.2.3 Recursive Step

Once has been computed for all pairs, the next level is:

Intuition: a path from to using states up to index either (a) never visits at all (captured by ), or (b) reaches for the first time (via ), loops through zero or more times (via ), and then leaves for the last time toward (via ).

This single recurrence is the heart of the algorithm; applying it for in order eventually produces for every accepting state .

1.3 Models for Languages: Operational vs. Generative

1.3.1 Two Fundamental Paradigms

Formal languages can be described in two fundamentally different ways:

• Operational models (automata) receive an input string and decide whether to accept or reject it. They are recognizers or transducers. Examples: FSA, PDA, Turing Machine.
• Generative models (grammars) provide a set of rewriting rules that can be applied to derive (generate) all and only the strings of a language. A grammar does not process input — it produces output.

Both paradigms describe the same underlying objects (formal languages), but from opposite directions. Each paradigm has advantages: automata are closer to implementation, while grammars are closer to specification.

1.3.2 Grammars in Parsing

In compiler construction, these two perspectives meet in parsing:

• A grammar (typically a context-free grammar or its BNF notation) defines the programming language syntax — it specifies what syntactically correct programs look like.
• An automaton (parser) processes source code — it reads the token stream and verifies that the program conforms to the grammar, recovering its syntactic structure for subsequent compilation phases.

Grammars may be nondeterministic in general, but actual parser generators (e.g., LL(1), LR(1)) often impose grammar restrictions and use limited lookahead to ensure deterministic parsing.

1.4 Chomsky Hierarchy

1.4.1 Classification of Grammars

Noam Chomsky (born 1928), the father of modern linguistics, introduced the formal classification of grammars in 1959. He observed that grammars differ in the form of their production rules, and that this form determines what class of languages the grammar can generate. His classification yields four nested types.

Chomsky hierarchy: nested language classes with their corresponding grammar types and automata

The four types form a strict hierarchy: every regular language is context-free, every context-free language is context-sensitive, and every context-sensitive language is recursively enumerable. The inclusions are proper — each class contains languages not in the class below it.

1.4.2 The Formal Definition of a Grammar

A grammar is a 4-tuple where:

• is a finite set of nonterminal symbols (variables);
• is a finite set of terminal symbols (the actual alphabet of generated strings), disjoint from ;
• is a finite set of production rules (rewriting rules);
• is the start symbol.

A derivation is a sequence of strings where each step replaces a substring of according to some rule in . The language generated by is:

That is, the set of all terminal strings derivable from the start symbol.

1.5 Grammar Types in Depth

1.5.1 Type-0: Unrestricted Grammars

Type-0 (general or unrestricted) grammars impose no restrictions on production rules beyond the one that the left-hand side must be non-empty:

Both and may be arbitrary strings of terminals and nonterminals. The prohibition on simply prevents generating symbols from nothing. All other grammar types are special cases of Type-0.

Type-0 grammars correspond to Turing Machines — they generate exactly the recursively enumerable languages (those that a TM can accept, though it may loop forever on strings not in the language).

1.5.2 Type-1: Context-Sensitive Grammars

Type-1 (context-sensitive) grammars require all production rules to have the form:

where is a nonterminal, and are (possibly empty) strings, and is a non-empty string. The key restriction is that must be non-empty — rules may not erase nonterminals (the grammar is non-contracting or monotone). The term context-sensitive reflects the fact that the nonterminal can only be rewritten in the specific context of on its left and on its right.

The canonical example is , which cannot be generated by any context-free grammar (intuitively: a single stack cannot count both the s against s and the s against s simultaneously). The corresponding machine model is the Linear Bounded Automaton (LBA), a Turing machine whose tape head is restricted to the portion of the tape occupied by the input.

Why “linear bounded”? The usable tape length is a linear function of the input length . For instance, allows two tape cells per input character. This bounded workspace corresponds precisely to the non-erasing constraint in context-sensitive grammars.

1.5.3 Type-2: Context-Free Grammars

Type-2 (context-free) grammars (CFGs) require all rules to have a single nonterminal on the left-hand side:

where and . The rewriting of is independent of its context — no matter what surrounds in the current string, the same set of rules applies. This is what “context-free” means.

CFGs are of paramount practical importance because they are equivalent to Backus-Naur Form (BNF), the notation used to specify the syntax of virtually all programming languages. The connection was discovered in 1960: the ALGOL-60 language, defined using BNF by John Backus and Peter Naur, was formally identical to Chomsky’s context-free languages.

BNF writes rules as <LHS> ::= <RHS>, where <LHS> is a nonterminal and <RHS> is any sequence of terminals and nonterminals. For example, the BNF rule <expr> ::= <expr> + <term> | <term> defines expressions as either sums or single terms.

Context-free languages are recognised by Nondeterministic Pushdown Automata (NPDAs). The stack provides exactly the “one level of nesting” needed to match balanced structures like parentheses or .

1.5.4 Type-3: Regular Grammars

Type-3 (regular) grammars impose the strictest constraints on production rules. All rules must be either right-linear or left-linear — but not a mix of both within the same grammar.

A right-linear grammar allows only rules of the form:

• (a string of terminals followed by at most one nonterminal), or
• (a string of terminals only).

A left-linear grammar allows only rules of the form:

• , or
• .

A grammar is regular if all its productions are right-linear, or all are left-linear; mixing the two orientations within one grammar is forbidden. Regular grammars generate exactly the regular languages — those accepted by Finite State Automata and described by regular expressions.

1.6 Correspondence Between Grammars and Automata

1.6.1 Regular Grammars and FSAs are Equivalent

The equivalence between Regular Grammars (RGs) and FSAs is constructive in both directions.

From FSA to RG. Given an FSA , construct as follows:

• (each state becomes a nonterminal);
• (the input alphabet becomes the terminals);
• (the initial state becomes the start symbol);
• For each transition , add rule ;
• For each accepting state , add rule .

The key invariant is if and only if .

From RG to FSA. Given , construct as follows:

• (nonterminals become states; add one extra accepting state);
• ;
• ;
• ;
• For each rule , add transition ;
• For each rule (no trailing nonterminal), add transition .

This construction confirms that Regular Grammars, Finite State Automata, and Regular Expressions are three equivalent formalisms for describing the same family of languages.

1.6.2 Context-Free Grammars and NDPDAs are Equivalent

Context-free grammars are equivalent to Nondeterministic Pushdown Automata. The proof is the theoretical core of compiler construction. The intuition is as follows: an NPDA can simulate the left-most derivation of a CFG by storing the current sentential form on the stack. When the top of the stack is a nonterminal , the NPDA non-deterministically applies one of ’s production rules (replacing on the stack with the right-hand side). When the top of the stack is a terminal , the NPDA reads the next input symbol and checks it matches.

Conversely, any NPDA can be converted to an equivalent CFG (this direction is more involved but equally constructive). Therefore:

1.6.3 Unrestricted Grammars and Turing Machines are Equivalent

General (unrestricted) grammars and Turing Machines recognise exactly the same class of languages — the recursively enumerable languages. Given a general grammar, a Turing Machine can simulate derivations by non-deterministically applying production rules. Conversely, given a Turing Machine, a general grammar can encode its configuration transitions as rewriting rules. This confirms the top of the Chomsky hierarchy.

1.6.4 Linear Bounded Automaton

A Linear Bounded Automaton (LBA) is a Turing Machine with one key restriction: the read/write head is constrained to remain within the portion of the tape occupied by the input string (bounded by end-markers [ and ]). The machine cannot access tape cells beyond the input boundaries.

The accessible tape length is a linear function of the input length — hence the name. An LBA for an input of length can use at most tape cells for some constant . This restricted workspace corresponds precisely to the non-contracting property of context-sensitive grammars. LBAs recognise exactly the context-sensitive languages.

1.7 Post Correspondence Problem

1.7.1 Definition

The Post Correspondence Problem (PCP), introduced by Emil Post in 1946, is one of the simplest examples of an undecidable problem. It is often used in computability theory as a stepping-stone for proving other problems undecidable (by reduction from PCP).

Input: Two lists and of strings over some alphabet.

Question: Does there exist a finite sequence of indices (each in , with ) such that:

That is, concatenating the -strings in the chosen order yields the same result as concatenating the -strings in the same order. A pair is called a corresponding pair.

1.7.2 The Problem is Undecidable

No algorithm can decide the Post Correspondence Problem for arbitrary inputs. This means there is no Turing Machine that, given any PCP instance , always halts and outputs “yes” if a solution exists and “no” otherwise. The PCP is therefore undecidable (like the Halting Problem), but it has the advantage of being simple to state without reference to Turing Machines or programs.

1.8 Computability Theory

1.8.1 The Two Central Questions

The theory of computation addresses two fundamental questions:

1. Mathematical: What can be computed? — Is there a mechanical procedure for solving this problem at all?
2. Engineering: How efficiently can it be computed? — How much time or memory does an algorithm require?

Computability theory addresses the first question. It studies the limits of mechanical problem solving, identifying which problems are solvable by any computational device and which are not — regardless of how powerful the device is or how much time it is given.

A useful metaphor: computability theory studies the speed of light of computer science — the fundamental ceiling that no computation can exceed. Just as physical laws constrain what is physically possible, computability limits what is mathematically computable.

1.8.2 The Church-Turing Thesis

The Church-Turing Thesis is the central claim of computability theory. It states (informally):

Any function that is intuitively computable by a systematic mechanical procedure can be computed by a Turing Machine.

This is a thesis (not a theorem) because “intuitively computable” is not a mathematical concept. The thesis cannot be proved, only supported by evidence: every computational model ever proposed (lambda calculus, partial recursive functions, RAM machines, quantum computers, etc.) has been shown to be equivalent in expressive power to Turing Machines, or strictly weaker.

The practical consequence: if we wish to show that some problem cannot be solved by any algorithm, it suffices to show it cannot be solved by a Turing Machine.

1.8.3 The Halting Problem and Undecidability

The Halting Problem is the question: given a program and an input , does terminate (halt) when run on ? Alan Turing proved in 1936 that no Turing Machine can solve the Halting Problem in general — it is undecidable.

A problem is decidable (also called recursive or computable) if there exists a Turing Machine that:

• halts and accepts for every input in the language, and
• halts and rejects for every input not in the language.

A problem is semi-decidable (recursively enumerable) if a Turing Machine accepts every input in the language but may loop forever on inputs not in the language.

A problem is undecidable if no Turing Machine can decide it. Undecidable problems exist; the Halting Problem and the Post Correspondence Problem are classic examples.

Decidability landscape: nested classes of computational problems

---

2. Definitions

• Thompson’s Construction: An algorithm that converts any regular expression into an equivalent ε-NFSA by recursively building automaton fragments for each subexpression and composing them using fixed rules for concatenation, union, and Kleene star.
• ε-NFSA (ε-Nondeterministic Finite State Automaton): An NFSA extended with ε-transitions — transitions that consume no input symbol, allowing the automaton to change state spontaneously.
• Kleene’s Algorithm: An algorithm that converts a finite state automaton into a regular expression by computing, for each state pair and each intermediate-state bound , the expression representing all paths from to through states of index at most .
• Grammar: A 4-tuple specifying a set of rewriting rules (productions) over nonterminal and terminal symbols that can derive strings of a language from the start symbol .
• Derivation: A sequence of strings where each step replaces a substring using one production rule. The derived language is the set of all terminal strings derivable from .
• Chomsky Hierarchy: A classification of formal grammars (and the languages they generate) into four nested types — Type 0 (unrestricted), Type 1 (context-sensitive), Type 2 (context-free), and Type 3 (regular) — each corresponding to a class of automata.
• Unrestricted Grammar (Type-0): A grammar with no restrictions on productions (other than ). Equivalent in power to Turing Machines; generates recursively enumerable languages.
• Context-Sensitive Grammar (Type-1): A grammar whose rules have the form (). The nonterminal is rewritten in the context of its surrounding strings. Equivalent to Linear Bounded Automata.
• Context-Free Grammar (Type-2): A grammar whose rules have the form — a single nonterminal rewrites to any string, regardless of context. Equivalent to Nondeterministic Pushdown Automata.
• Backus-Naur Form (BNF): A notation for context-free grammars used to specify programming language syntax, writing rules as <nonterminal> ::= <RHS>. Formally equivalent to CFGs.
• Regular Grammar (Type-3): A grammar whose rules are all right-linear ( or ) or all left-linear ( or ); mixing orientations is forbidden. Equivalent to FSAs and regular expressions.
• Right-linear Grammar: A grammar where every rule has the form or ; the nonterminal (if any) always appears at the right end of the right-hand side.
• Left-linear Grammar: A grammar where every rule has the form or ; the nonterminal (if any) always appears at the left end of the right-hand side.
• Linear Bounded Automaton (LBA): A Turing Machine whose read/write head is restricted to the tape cells occupied by the input (bounded by end-markers). LBAs recognise exactly the context-sensitive languages.
• Parsing: The process of using an automaton (parser) to verify that an input string (program) conforms to a grammar (language specification) and to recover its syntactic structure.
• Post Correspondence Problem (PCP): The problem of determining, given two equal-length lists of strings and , whether there exists a finite sequence of indices such that concatenating the -strings in that order equals concatenating the -strings in the same order. The PCP is undecidable.
• Computability Theory: The branch of theoretical computer science that studies which problems can (and cannot) be solved by any mechanical computational procedure, regardless of time or memory.
• Decidable Problem: A problem for which there exists a Turing Machine that always halts and correctly answers “yes” or “no” for every input.
• Semi-decidable Problem: A problem for which a Turing Machine accepts every positive instance but may loop forever on negative instances. Also called recursively enumerable.
• Undecidable Problem: A problem for which no Turing Machine can decide it. No algorithm exists that correctly answers all instances.
• Church-Turing Thesis: The claim that every intuitively computable function can be computed by a Turing Machine — equivalently, that Turing Machines capture the full extent of mechanical computation.

---

3. Formulas

• Kleene’s Algorithm — initial step ():
• Kleene’s Algorithm — recursive step:
• Language accepted by FSA via Kleene:
• Thompson’s Construction — Union:
• Thompson’s Construction — Kleene Star:

---

4. Practice

4.1. Construct ε-NFSA for (Lab 11, Example 1)

Build the ε-NFSA for the regular expression using Thompson’s Construction.

Click to see the solution

Step 1 — Build . The symbol maps to a two-state automaton:

N(1): automaton for the symbol 1

Step 2 — Build . Similarly for the symbol :

N(0): automaton for the symbol 0

Step 3 — Build by concatenation. Merge with :

N(01): concatenation of N(0) and N(1)

Step 4 — Build by union. Introduce a new start state with -transitions into and , and a new accepting state with -transitions from both accepting states:

The resulting automaton has states with:

• (the branch);
• (the branch).

Step 5 — Apply Kleene star. Introduce a new start state and new accepting state :

• (enter the union automaton);
• (loop back for another repetition);
• (bypass for zero repetitions);
• (accept after one or more repetitions).

Complete N((1|01)*): full ε-NFSA produced by Thompson’s Construction

Answer: The ε-NFSA has 9 states and recognises exactly — all strings formed by concatenating zero or more words from .

4.2. Apply Kleene’s Algorithm to a 2-State FSA (Lab 11, Example 2)

Find a regular expression for the language accepted by the FSA with states , where is both the start state and the only accepting state, and transitions are: , , .

The 2-state FSA for Kleene’s Algorithm example

Click to see the solution

Step (initial expressions).

Inspect each pair of states:

• : from to , direct transitions. , so the symbol is a self-loop. Since : .
• : from to , direct transitions. : .
• : from to , direct transitions. : .
• : from to , no self-loop transition. Since and no real symbol loops: .

Step (allow intermediate state ).

Apply the recurrence .

• Simplification: , and . Any finite number of s is accepted, including zero.

• Going from to (possibly looping) and then taking the -transition to .

• Taking the -transition from to , then optionally looping in .

• Reaching via , looping, then going back to via ; or staying in with zero moves.

Step (allow intermediate state ).

The only accepting state is , so we only need . Apply:

Substituting:

Simplification: (since any sequence of the pattern including zero repetitions). Also . So:

Since and (two states, indexed and ), the final answer is :

Interpretation: the language consists of all strings of s and s that either (a) contain only s (ending in by looping), or (b) contain at least one and end with a block of s — strings that always return to before the end.

4.3. Build ε-NFSA for (Lab 11, Task 1)

Using Thompson’s Construction, build an ε-NFSA for the regular expression .

Click to see the solution

Step 1 — Build : a two-state automaton with a -transition.

Step 2 — Build : a two-state automaton with a -transition.

Step 3 — Build by Kleene star. Introduce new start and new accept :

• (loop);
• (exit);
• (bypass for zero s).

Step 4 — Build by concatenation. Chain into by merging the accepting state of with the start state of :

ε-NFSA for 01*: a 0-transition followed by zero or more 1-transitions

The automaton accepts exactly the strings .

4.4. Build ε-NFSA for (Lab 11, Task 2)

Using Thompson’s Construction, build an ε-NFSA for the regular expression .

Click to see the solution

Step 1 — Build by union. Introduce start with -transitions to and , and accept with -transitions from both:

Step 2 — Build by concatenating with and then .

Chain: the accepting state of connects to the start of , which connects to :

εε

The full automaton: 1. Start at . 2. Non-deterministically read or (the union fragment), reaching . 3. Read , reaching an intermediate state. 4. Read , reaching the accepting state .

The automaton accepts strings of length 3 of the form followed by : the language .

4.5. Build ε-NFSA for (Lab 11, Task 3)

Using Thompson’s Construction, build an ε-NFSA for .

Click to see the solution

Step 1 — Build twice (two separate fragments for the leading ).

Step 2 — Build using the union rule (same as Task 2, Step 1).

Step 3 — Build using the Kleene star rule: introduce (loop) and , .

Step 4 — Build by concatenating , , and :

ε-NFSA for 00(0|1)*: two leading 0-transitions then a loop accepting any binary suffix

The automaton accepts all strings starting with followed by any (possibly empty) binary string — i.e., .

4.6. Apply Kleene’s Algorithm to FSA 1 (Lab 11, Task 4)

Find a regular expression for the FSA with states , where is the only accepting state, and transitions: (self-loop), , (self-loop).

FSA for Task 4: accepting state q₁

Click to see the solution

Step :

• (self-loop on , plus for staying).
• (direct -transition to ).
• (no transition from to ).
• (self-loop on ).

Step (allow intermediate ):

Step (allow intermediate ):

We need (path from start to accept ):

Since : .

Interpretation: the language is all strings of the form (zero or more s), then (one or more s). The automaton accepts strings that consist of any number of leading s followed by at least one .

4.7. Apply Kleene’s Algorithm to FSA 2 (Lab 11, Task 5)

Find a regular expression for the FSA with states , where is the start and only accepting state, and transitions: (self-loop), , (self-loop), .

FSA for Task 5: accepting state q₀

Click to see the solution

Step :

Step :

Step :

Since : .

Interpretation: the automaton is in whenever it has read an even number of s (and any number of s between them). The language is exactly all binary strings with an even number of s.

4.8. Regular Expression for 3-State FSA (Homework 11, Task 1)

Find a regular expression that describes the language accepted by the FSA with states , where is both the start state and only accepting state, and transitions: (self-loop), , (self-loop), , , .

3-state FSA for Homework Task 1

Click to see the solution

Step :

• (both and go from to )

Step (allow ):

Since and , any path using as intermediate from or back contributes . So:

Step (allow and ):

Step (allow all states; we need ):

First compute :

And

Since , the product . Therefore:

Answer: .

Interpretation: the only strings accepted are sequences of s (including the empty string). Any immediately takes the automaton out of the accepting state , and there is no way back to from or . The accepting state can only be revisited via a path , which never returns to . So only pure strings of s are accepted.

4.9. Build ε-NFSA for (Homework 11, Task 2)

Using Thompson’s Construction, build an ε-NFSA for .

Click to see the solution

Step 1 — Build (two-state, -transition).

Step 2 — Build by concatenation of two copies of :

Step 3 — Build by Kleene star:

Introduce and :

• (loop);
• (exit);
• (bypass).

Step 4 — Build by union:

Step 5 — Concatenate and :

Merge with . The final automaton has 10 states.

ε-NFSA for (11)*(0|1): any even number of 1s followed by a single 0 or 1

The automaton accepts strings consisting of an even number of s (including zero) followed by a single bit: .